package 数据结构OJ;

import java.util.*;
/**
 * @author shy_black
 * @date 2019/7/28 17:09
 * @Description:
 *      首先明确--> 需求为将二叉树的每一层节点值放入一个链表中，
 *         每一层节点又可以作为一个链表进行存储，所有先创建一个ArrayList<ArrayList<Integer>> queue
 *             而后创建ArrayList<Integer> out，作为queue的存储元素
 *             LinkedList<TreeNode> tree为作为真实运算每一层元素的的节点队列
 *             当tree链表不为空时，进行以下循环：
 *             now-->标记本层父节点元素个数，初始为1，当now==0时，表示本层元素已经遍历完毕
 *             next-->标记子节点元素个数，每加入一个子节点元素，next++，当本层元素遍历结束后（即now== 0）
 *             将存储本层元素的链表out作为queue的元素存储（queue.add(out)）,随后next赋值给now，意为开始下一次遍历
 *             next赋值0，重新开始计算子节点元素个数。
 *
 */
public class 把二叉树打印成多行 {


 class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {

        ArrayList<ArrayList<Integer>> queue = new ArrayList<> ();
        ArrayList<Integer> out = new ArrayList<>();
        LinkedList<TreeNode> tree = new LinkedList<>();
        tree.add(pRoot);
        int now = 1;
        int next = 0;
        if(pRoot == null)
            return queue;

        while(!tree.isEmpty()) {
            TreeNode cur = tree.remove();
            out.add(cur.val);
            now--;
            if(cur.left != null) {
                tree.add(cur.left);
                next++;
            }
            if(cur.right != null) {
                tree.add(cur.right);
                next++;
            }
            if(now == 0) {
                queue.add(out);
                out.clear();
                now = next;
                next = 0;
            }
        }
        return queue;


    }
}